1. Field of the Invention
This invention relates generally to methods of processing directed graphs within a computer system, wherein the vertices represent electrical components of a system and the arcs represent physical or logical relationships between the components. The invention is more specifically related to a method for generating a preferred order for processing the vertices of a directed graph for use by Computer Aided Engineering (CAE) simulation tools and for detecting cycles in a directed graph.
2. Background Information
In recent years, many advanced Computer Aided Engineering (CAE) analysis and simulation tools have been developed to facilitate the design of Very Large Scale Integrated (VLSI) circuits. The goals of applying these CAE tools include improving product quality, improving product safety, reducing engineering time by needing fewer design iterations, reducing the number of prototypes or possibly eliminating the need for prototypes, and reducing product cost.
It is axiomatic that engineering analyses can be used to evaluate and predict the behavior of new designs. Historically, engineers analyzed designs by performing calculations by hand or with a computing aid such as a electronic calculator. They frequently used tabulated mathematical functions, approximation methods, and data accumulated from previous experience and physical testing to simplify their analyses. Some analyses were so time-consuming that, when done at all, they could only be completed for simple systems. This frequently led to under- and overdesigned systems. In the first case, this created systems that did not work properly, failed outright, or were physically impossible to build. In the second case, the systems were more expensive than necessary or did not meet their performance requirements.
The advent of advanced computer-based logic design tools solved these problems by allowing a system designer to easily specify a complex electronic system, via a language such as Very High Speed Integrated Circuits Hardware Description Language (VHDL), by selecting its electrical components from a standard-parts library of electrical components and by connecting the components together to form the desired electronic system or device. The CAE libraries include standard electrical components, their physical characteristics, performance criteria, and specifications. The use of these standard-parts libraries in conjunction with CAE tools greatly simplifies the process of setting up a simulation or other analysis of the system design. Modern CAE tools allow design engineers to analyze, evaluate, and verify the functionality and physical characteristics of a design for a circuit board, VLSI chip, or other electrical or electronic device before it is committed to manufacturing. In some cases, the CAE simulation supplants altogether the building of a prototype. Available analyses include gate level, switching, electrical level, analog-to-digital conversion, worst case statistical, and sensitivity-base simulations. Partly as a result of using such tools, the density and complexity of many systems has risen dramatically. Many system designs contain hundreds of thousands of electrical components with their accompanying connections perhaps numbering in the millions. Obviously, testing and verification of these complex system designs are daunting tasks for human beings, and computerized methods must be as efficient as possible so as to minimize the time needed to verify a design.
Various models are typically used by the CAE tools to represent the components of the system being designed, their interrelationships, and their characteristics. Hierarchical representation of components in a model implemented by the CAE tool provides multiple levels of logical abstraction of the system and hence is a preferred methodology for use in complex system design. However, it is usually difficult to derive information about the system from the different levels of the model. Consequently, redundant representations of electrical components may exist. One potential problem with a complex system design as specified by the various design engineers using the CAE tool may be that the entire system physically cannot be manufactured as designed. This situation could arise if one design engineer has specified a particular component to be a part of the system at a particular level of abstraction of the system hierarchy, and the same or another logic designer working on the system specifies the same component to be a part of the system at a lower level of the system hierarchy, such that the second instance of the component is logically contained (and subsequently physically contained) within the first instance of the component. This design error may result in the attempted manufacture of a system that does not work and actually cannot physically be built. This logical inconsistency may be easily detected for simple system designs, but when the number of components grows very large, the difficulty in detecting errors increases exponentially.
The model of the system components, their interrelationships and characteristics, are commonly represented in a CAE tool being executed by a computer system as a directed graph. A graph is a non-empty but finite set of edges that join pairs of distinct vertices. A directed graph is obtained if direction is added to each edge of a graph. The edges form a finite set of ordered pairs of distinct vertices. For directed graphs, these edges are usually called arcs. Graphs are used extensively to represent the structure of a system. Graphs are simple abstractions of reality, and are useful in enhancing the understanding of complex systems. The vertices usually represent objects of some kind (such as electrical components) and the arcs represent connections of a physical or logical nature between the vertices (such as the inclusion of one component by another). A useful representation of the set of arcs defining a directed graph is called an adjacency list. An arc sequence with distinct arcs is called a path. A path in which all vertices are distinct is called a simple path. A closed path, that is, a path having the first vegex equal to the last vertex, in the arc sequence is called a cycle. A directed acyclic graph is a directed graph that has no cycles. A directed acyclic graph is called a tree if it has a unique vertex (the root), which no arcs enter, every other vertex has exactly one arc entering it, and there is a unique path from the root to any vertex.
It is important to determine if a directed graph representing a complex system has a cycle. If the vertices of a directed graph represent hardware components such as registers, multiplexors, arithmetic logic units (ALUs), gates, flip-flops, etc., and the arcs of the directed graph represent the physical inclusion of one component into another, the existence of a cycle is evidence of a physical impossibility in the design. Detecting this situation early in the design cycle reduces the cost of fixing the problem at the testing stage, or worse yet, during the manufacturing process. Detecting a cycle in a directed graph and determining a preferred processing order of the vertices of the graph are common problems and there are many possible solutions. Most solutions, however, require that the vertices be connected to their arcs in the data structures used to represent the vertices and arcs in the CAE tool, that the vertices or arcs be sorted in a particular order, or involve time consuming searches through the data structures. Such existing solutions typically have computational complexities of O(n**2), where n is the number of arcs. Therefore, as the number of arcs and vertices grows large, the processing time for implementation of these solutions grows exponentially. Of course, when a complex system is being designed that has an extremely large number of components and the computational complexity of the simulation is exponential, the processing time required may become prohibitive. In that case, validation of the system design is not completed at the risk of having a fatal defect in the design being discovered on the manufacturing floor. A method for detecting cycles in a directed graph that has a linear computational complexity of O(n) is highly desirable in that it substantially and dramatically reduces the processing time needed to analyze and validate a large, complex system design. The present invention delivers the performance benefits from achieving this linear computational complexity for simulating complex system designs.